Fragmentation (computing)

In computer storage, fragmentation is a phenomenon in which storage space is used inefficiently, reducing storage capacity and in most cases reducing the performance. The term is also used to denote the wasted space itself.

There are three different but related forms of fragmentation: external fragmentation, internal fragmentation, and data fragmentation. Various storage allocation schemes exhibit one or more of these weaknesses. Fragmentation can be accepted in return for increase in speed or simplicity.

Contents 1 Memory fragmentation 1.1 Basic principle 1.2 Types of memory fragmentation 1.3 Overhead 1.4 Internal fragmentation 1.5 External fragmentation 2 Data fragmentation 3 Performance degradation due to fragmentation 4 References 5 External links 6 See also

Memory fragmentation

Basic principle

"Fragmented memory" denotes all of the system's unusable free memory. Memory fragmentation usually occurs when memory is allocated dynamically (using calls like malloc). Generally, memory allocation performed during runtime is not in the form of stacks. The memory allocator wastes memory in the following ways:

• 1. Overhead
• 2. Internal Fragmentation
• 3. External Fragmentation.

When blocks of memory are allocated during runtime, it is highly unlikely that these released blocks of memory will again form continuous large memory blocks. Hence, the free memory gets interspersed with the blocks of memory in use. The average size of blocks of memory consequently becomes quite small. This problem, coupled with incomplete usage of the allocated memory, results in memory fragmentation.

For example, consider a system having 5 MB total memory. Let the total free memory be 2 MB which the programs could use at runtime. However, due to interspersed free and used memory blocks the user is not able to allocate even 1 MB of free space for a new program as all the free memory blocks are not larger than 500 KB. Also, if in the 3 MB allocated memory only 2 MB is used then the remaining 1 MB memory goes unused. This wastage of space is the major problem of internal and external memory fragmentation.

Types of memory fragmentation

Overhead

The memory allocator needs to store all the information related to all memory allocations. This information includes the location, size and ownership of any free blocks, as well as other internal status details. Overhead comprises of all the additional system resources that the programming algorithm requires. A dynamic memory allocator typically stores this overhead information in the memory it manages. This leads to wastage of memory. Hence, it is considered as a part of memory fragmentation.

Internal fragmentation

When the memory allocated is larger than required, the rest is wasted. Some reasons for excess allocation are:

• 1. Allocator policy - involves architectural constraints,
• 2. A client asks for more memory than is required.

The term "internal" refers to the fact that the unusable storage is inside the allocated region. While this may seem foolish, it is often accepted in return for increased efficiency or simplicity.

1. There are some basic memory allocation rules involved. All memory allocators must adhere to it. According to the "segregated free list" allocator policy, all memory allocations must start at an address divisible by 4, 8, or 16. The memory allocator may assign blocks of only certain predefined sizes to clients. It depends upon the processor architecture. Also, extra bytes are assigned to a program for alignment and metadata.

For example, when a client requests a block of 23 bytes, it may well get 24 or 28 bytes or even more.

Or in many file systems, each file always starts at the beginning of a cluster, because this simplifies organization and makes it easier to grow files. Any space left over between the last byte of the file and the first byte of the next cluster is a form of internal fragmentation called file slack, slack space or cluster overhang.^[1][2] Slack space is a very important source of evidence in computer forensic investigation.

Another common example: English text is often stored with one character in each 8-bit byte even though in standard ASCII encoding the most significant bit of each byte is always zero. The unused bits are a form of internal fragmentation.

Similar problems with leaving reserved resources unused appear in many other areas. For example, IP addresses can only be reserved in blocks of certain sizes, resulting in many IPs that are reserved but not actively used. This contributes to the IPv4 address shortage.

Unlike other types of fragmentation, internal fragmentation is difficult to reclaim; usually the best way to remove it is with a design change. For example, in dynamic memory allocation, memory pools drastically cut internal fragmentation by spreading the space overhead over a larger number of objects.

External fragmentation

External fragmentation is the inability to use free memory as the free memory is divided into small blocks of memory and these blocks are interspersed with the allocated memory. It is a weakness of certain storage allocation algorithms, occurring when an application allocates and deallocates ("frees") regions of storage of varying sizes, and the allocation algorithm responds by leaving the allocated and deallocated regions interspersed. The result is that although free storage is available, it is effectively unusable because it is divided into pieces that are too small to satisfy the demands of the application. The term "external" refers to the fact that the unusable storage is outside the allocated regions.

For example, consider a situation wherein a program allocates 3 continuous blocks of memory and then frees the middle block. The memory allocator can use this free block of memory for future allocations. However, it cannot use this block if the memory to be allocated is larger in size than this free block.

External fragmentation also occurs in file systems as many files of different sizes are created, change size, and are deleted. The effect is even worse if a file which is divided into many small pieces is deleted, because this leaves similarly small regions of free spaces.

0x0000	0x1000	0x2000	0x3000	0x4000	0x5000	Comments
						Start with all memory available for allocation.
A	B	C				Allocated three blocks A, B, and C, of size 0x1000.
A		C				Freed block B. Notice that the memory that B used cannot be included for an allocation larger than B's size.

As compared to external fragmentation, overhead and internal fragmentation account for little loss in terms of wasted memory and reduced performance. External fragmentation does the most damage to the system. It is defined as:

External fragmentation is the factor between 0 to 1. A 100% fragmentation (factor = 1) suggest that the system is completely out of usable free memory. While a 0 factor (0% fragmentation) denotes that all the free memory is in a single large block.

For example, fragmentation is 90% when 100 MB free memory is present but largest free block of memory for allocation is just 10 MB.

Data fragmentation

Data fragmentation occurs when a piece of data in memory is broken up into many pieces that are not close together. It is typically the result of attempting to insert a large object into storage that has already suffered external fragmentation.

For example, files in a file system are usually managed in units called blocks or clusters. When a file system is created, there is free space to store file blocks together contiguously. This allows for rapid sequential file reads and writes. However, as files are added, removed, and changed in size, the free space becomes externally fragmented, leaving only small holes in which to place new data. When a new file is written, or when an existing file is extended, the operating system puts the new data in new non-contiguous data blocks to fit into the available holes. The new data blocks are necessarily scattered, slowing access due to seek time and rotational latency of the read/write head, and incurring additional overhead to manage additional locations. This is called file system fragmentation.

When writing a new file of a known size, if there are any empty holes that are larger than that file, the operating system can avoid data fragmentation by putting the file into any one of those holes. There are a variety of algorithms for selecting which of those potential holes to put the file; each of them is a heuristic approximate solution to the bin packing problem. The "best fit" algorithm chooses the smallest hole that is big enough. The "worst fit" algorithm chooses the largest hole. The "first-fit algorithm" chooses the first hole that is big enough. The "next fit" algorithm keeps track of where each file was written.

As another example, if the nodes of a linked list are allocated consecutively in memory, this improves locality of reference and enhances data cache performance during traversal of the list. If the memory pool's free space is fragmented, new nodes will be spread throughout memory, increasing the number of cache misses.

Just as compaction can eliminate external fragmentation, data fragmentation can be eliminated by rearranging data storage so that related pieces are close together. For example, the primary job of a defragmentation tool is to rearrange blocks on disk so that the blocks of each file are contiguous. Most defragmenting utilities also attempt to reduce or eliminate free space fragmentation. Some moving garbage collectors will also move related objects close together (this is called compacting) to improve cache performance.

Performance degradation due to fragmentation

Memory fragmentation is one of the most severe problems faced by system managers. Over time, it leads to degradation of system performance. Eventually memory fragmentation leads to complete loss of free memory.

Memory fragmentation is a kernel programming level problem. It becomes a critical issue when it reaches alarming levels. A real life example is of 99% fragmentation which frequently occurs during Real-time computing of applications. This fragmentation occurs just seconds before the System crashes. It is difficult to avert this System crash as it is impossible to anticipate the critical rise in levels of memory fragmentation.

According to a research conducted by International Data Corporation, the performance degradation is largely due to external fragmentation. The life-time of server is shortened by 33% by external fragmentation alone. This leads to a direct increase of 33% in the yearly budget for hardware upgrades. Thus it can be concluded that memory fragmentation has an undesirable effect not only on memory usage and processing speed of the System but also on hardware components and cost of project.

References

1. ^ FAT Partition Efficiency: Slack
2. ^ http://service1.symantec.com/support/on-technology.nsf/854fa02b4f5013678825731a007d06af/ec7ee0df20ad4f7a8825734e0059c256?OpenDocument

1. http://www.edn.com/article/478952-Handling_memory_fragmentation.php
2. http://www.sqlservercentral.com/articles/performance+tuning/performancemonitoringbyinternalfragmentationmeasur/2014/
3. C++ Footprint and Performance Optimization, R. Alexander; G. Bensley, Sams Publisher, First edition, Page no:128, ISBN no:9780672319044
4. Ibid, Page no:129

External links

• Videos explaining the concept of slack space, Department of Computer Systems and Communications, UTM

See also

• Defragmentation
• File system fragmentation
• Memory management

Memory management Manual memory management Delete (C++) C dynamic memory allocation new (C++) Static memory allocation Virtual memory Demand paging Page table Paging Hardware Memory management unit Translation lookaside buffer Garbage collection Finalizer Garbage Reference counting Strong reference Weak reference Implementations Boehm garbage collector Garbage-first collector Memory segmentation Protected mode Real mode Virtual 8086 mode x86 memory segmentation Memory safety Buffer overflow Dangling pointer Stack overflow Issues Fragmentation Memory leak Unreachable memory Other Automatic variable International Symposium on Memory Management Region-based memory management